//// encode: utf-8 (It is best to open using vscode)
// reference video: https://www.bilibili.com/video/BV1MV411e7WZ

#include <iostream>
#include <algorithm>

typedef struct Action
{
    int begin;
    int end;
    int index;
} Action;

// Use Predicate
class MyCmp
{
public:
    bool operator()(const Action &a, const Action &b)
    {
        return a.end <= b.end;
    }
};

// Not Use Predicate
// bool MyCmp(const Action &a, const Action &b)
// {
//     return a.end <= b.end;
// }

class Solution
{
public:
    Action m_Action[100]{};
    int m_ActionNums{};
    bool m_Flag[100]{false};

public:
    void GreedySelector()
    {
        std::sort(m_Action + 1, m_Action + 1 + m_ActionNums, MyCmp()); // Use Predicate
        // std::sort(m_Action + 1, m_Action + 1 + m_ActionNums, MyCmp);   // Not Use Predicate
        m_Flag[1] = true;
        int preEnd = 1;
        for (int i = 2; i <= m_ActionNums; i++)
        {
            if (m_Action[i].begin >= m_Action[preEnd].end)
            {
                m_Flag[i] = true;
                preEnd = i;
            }
        }
    }

    void Print()
    {
        for (int i = 1; i <= m_ActionNums; i++)
        {
            if (m_Flag[i])
            {
                std::cout << m_Action[i].index << " ";
            }
        }
        std::cout << std::endl;
    }
};

int main()
{
    Solution slt;

    std::cout << "Please enter the number of activities" << std::endl;
    std::cin >> slt.m_ActionNums;

    std::cout << "Please enter the start and end time of the activity" << std::endl;

    for (int i = 1; i <= slt.m_ActionNums; i++)
    {
        std::cin >> slt.m_Action[i].begin >> slt.m_Action[i].end;
        slt.m_Action[i].index = i;
    }

    slt.GreedySelector();
    slt.Print();
}
